#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;

//单词拆分
//https://leetcode.cn/problems/word-break/
//class Solution {
//public:
//    bool wordBreak(string s, vector<string>& wordDict) {
//        int n = s.size();
//        unordered_set<string> hashs(wordDict.begin(), wordDict.end());
//        vector<bool> vb(n + 1); //默认初始化为false
//        vb[0] = true; //为了不让多加的位置妨碍计算 第一个位置为true(即[1,i]满足时 单独成为一个字串)
//        s = ' ' + s; //在原串前加一个空格 统一下标从1开始(因为我们会用到 j-1)
//
//        for (int i = 1; i <= n; ++i)
//            for (int j = i; j >= 1; --j)
//            {
//                //开始判断每一组  一组由[0,j-1]和[j,i] 随着j减小 [j,i] 的字符串会变长
//                //当[0,j-1] 中在vb中满足(以前成功组成字符串) 且[j,i]字符串在字典中则[0,i]字符串满足
//                if (vb[j - 1] && hashs.count(s.substr(j, i - j + 1))) //如果 [0,j-1] 和 [j,i] 可以组成字符串则满足
//                {
//                    vb[i] = true;
//                    break;
//                }
//            }
//        return vb[n];
//    }
//};



//环绕字符串中唯一的子字符串
//https://leetcode.cn/problems/unique-substrings-in-wraparound-string/
// class Solution {
// public:
//     int findSubstringInWraproundString(string s) {
//         int n = s.size();
//         if(n == 1) return 1;

//         vector<int> v(n,1); //因为每个单独的字母一定在base中出现，所以肯定为1
//         int arr[26] = {0}; //字符串去重数组(相同字母结尾的字符串求最大值即可)
//         for(int i = 1;i<n;++i)
//             //如果前面的字符与后面字符相连则+1
//             if(s[i-1]+1==s[i] || s[i-1]=='z' && s[i] == 'a') 
//                 v[i] = v[i-1]+1;

//         for(int i = 0;i<n;++i) //开始去重
//             //如果字符串中出现相同字母，例如cac，取c结尾字符的最大子字符串数即可
//             arr[s[i]-97] = max(arr[s[i]-97],v[i]);
        
//         int ret = 0;
//         for(int i = 0;i<26;++i) ret += arr[i];

//         return ret;
//     }
// };


//最长递增子序列 - 动态规划解法
//https://leetcode.cn/problems/longest-increasing-subsequence/
// class Solution {
// public:
//     int lengthOfLIS(vector<int>& nums) {
//         int n = nums.size();
//         if(n == 1) return 1;

//         //dp表初始化为最坏的情况 即每一个子序列都不递增 都为1
//         vector<int> v(n,1);
//         int num = 0;
//         for(int i = 0;i<n;++i)
//         {
//             //在前面的子序列中找是否可以组成连续的子序列
//             for(int j = 0;j<i;++j)
//             {
//                 if(nums[i] > nums[j])
//                     v[i] = max(v[j]+1,v[i]);
//             }
//             num = max(num,v[i]);
//         }
//         return num;
//     }
// };